package Cluedo.Game;

import java.util.Vector;
import java.util.Hashtable;

/**
 * An essential class for the Game model, this stores all nodes in the graph representing the board.
 * it also performs all search operations.
 *  
 * @author Alex Ellis
 *
 */
public class Map {
	private Board lnkBoard;

	/**
	 * All existing nodes in the game.
	 * 
	 */
	Vector positions = new Vector();
	
	Position foundPosition = null;
	
	/**
	 *  Used in shortest path functions
	 */
	int shortestPath = -1;
	/**
	 *  Used in shortest path functions
	 */
	Vector shortestPathRoute = new Vector();
	/**
	 * 	Used in shortest path functions
	 */
	boolean pathFound = false;
	int mapDebug = 0;
	
	/**
	 * Get all the map nodes in the game.
	 * 
	 * @param type
	 * specify "rooms" or "" for all
	 * @return the nodes in the map
	 */
	public Vector getNodes(String type) {
		Vector result = new Vector();

		if(type.equals("rooms")) {
			result = vectorCopy( positions );
			for(int i = 0; i < positions.size(); i++)
				if(!(positions.elementAt(i) instanceof Room))
					result.remove(positions.elementAt(i));
			return result;
		}
		return positions;
	}
	/**
	 * @return Simply all nodes in map.
	 */
	public Vector getNodes() {
		return positions;
	}
	public void setNodes(Vector nodes) {
		positions = vectorCopy(nodes);
	}
	
	  /**
	   * Does what it says on the tin.
	   * @param passedNodes
	   * @return a new vector
	   */
	  public Vector vectorCopy(Vector passedNodes) {
		 	Vector vcopy = new Vector();
		 	for(int i = 0; i < passedNodes.size(); i++)
		 		vcopy.add(passedNodes.elementAt(i));
		 	
		 	return vcopy;
	  }


	/**
	 * Searches all positions and returns an object based on its ID
	 * 
	 * @return Position corresponding to ID 
	 */
	 public Position findByID(String ID) {
	  	for(int i = 0; i < positions.size(); i++)
	 		if(((Position) positions.elementAt(i)).getID().equals(ID)) {
	 			return (Position) positions.elementAt(i);
	 		}
	 		
		return null;
	 }
	 /**
	  * Binding is reciprocal and joins to nodes together.
	  * 
	  * @param target
	  * Source
	  * @param bind
	  * Target
	  */
	 public void bind(String target, String bind) {
	 	// Binding is reciprocal
	 	Position targetPointer = findByID(target);
	 	Position bindPointer = findByID(bind);

	 	if(targetPointer != null && bindPointer != null) {
	 		targetPointer.addNeighbour(bindPointer);
	 		bindPointer.addNeighbour(targetPointer);
	 	}
	 }

	private void printPath(Vector pathTaken) {
		for(int i =0;i<pathTaken.size();i++)
			System.out.print(
				((Position)pathTaken.elementAt(i)).getID() + " > "
				);

		System.out.print("\n");	
	}

	// Holds backwards mappings from the destination node.
	Hashtable fathers;

//	public int pathTo(Position src, Position dest) {
//		Vector queue = new Vector();
//		Vector passed = new Vector();
// 		fathers = new Hashtable();
// 		
//		passed.add(src);
//				
//
//		for(int i =0;i<src.getNeighbours().size();i++) {
//			Position u = (Position)src.getNeighbours().elementAt(i);
//			
//			fathers.put(u.getID(), src);
//			queue.add(u);
//		}
//		
//		//int len = pathTo(src,dest,queue,passed);
//		
//		int len = validPathTo(src,dest,queue,passed);
//
//		// Trace-back all the fathers of nodes and build a path
//				
//		Vector pathTaken = new Vector();
//		
//		Position trace = (Position)fathers.get(dest.getID());
//		pathTaken.add(0,dest);
//		while(trace != null && trace!=src) {
//			pathTaken.add(0,trace);
//			trace = (Position)fathers.get(trace.getID());
//		}
//		if(trace == null)
//			System.out.println("no route exists");
//		pathTaken.add(0,src);
//		
//		//printPath(pathTaken);
//	
//		return len;
//	}
	
	public Vector routeTo(Position src, Position dest) {
		Vector queue = new Vector();
		Vector passed = new Vector();
 		fathers = new Hashtable();
 		
		passed.add(src);
				

		for(int i =0;i<src.getNeighbours().size();i++) {
			Position u = (Position)src.getNeighbours().elementAt(i);
			if(u.isOccupied() == true && !( u instanceof Room)) {
				passed.add(u);
				continue;
			}
			fathers.put(u.getID(), src);
			queue.add(u);
		}
		
		int len = validPathTo(src,dest,queue,passed);

		// Trace-back all the fathers of nodes and build a path
				
		Vector pathTaken = new Vector();
		
		Position trace = (Position)fathers.get(dest.getID());
		pathTaken.add(0,dest);
		while(trace != null && trace!=src) {
			pathTaken.add(0, trace);
			trace = (Position)fathers.get(trace.getID());
		}
		if(trace == null) {
//			System.out.println("no route exists");
			return new Vector();
		}
		
		
		pathTaken.add(0,src);

		return pathTaken;
	}
	
	
	public Vector illegalRouteTo(Position src, Position dest) {
		Vector queue = new Vector();
		Vector passed = new Vector();
 		fathers = new Hashtable();
 		
		passed.add(src);
				

		for(int i =0;i<src.getNeighbours().size();i++) {
			Position u = (Position)src.getNeighbours().elementAt(i);

			fathers.put(u.getID(), src);
			queue.add(u);
		}
		
		int len = illegalPathTo(src,dest,queue,passed);

		// Trace-back all the fathers of nodes and build a path
				
		Vector pathTaken = new Vector();
		
		Position trace = (Position)fathers.get(dest.getID());
		pathTaken.add(0,dest);
		while(trace != null && trace!=src) {
			pathTaken.add(0, trace);
			trace = (Position)fathers.get(trace.getID());
		}
		if(trace == null) {
//			System.out.println("no route exists");
			return new Vector();
		}
		
		
		pathTaken.add(0,src);

		return pathTaken;
	}
	
	
	
//	public int shortestPathTo(Position src, Position dest) {
//		Vector queue = new Vector();
//		Vector passed = new Vector();
// 		fathers = new Hashtable();
// 		
//		passed.add(src);
//				
//
//		for(int i =0;i<src.getNeighbours().size();i++) {
//			Position u = (Position)src.getNeighbours().elementAt(i);
//			if(u.isOccupied() == true && !( u instanceof Room)) {
//				passed.add(u);
//				continue;
//			}
//			fathers.put(u.getID(), src);
//			queue.add(u);
//		}
//		
//		int value = validPathTo(src,dest,queue,passed);
//		Position trace = (Position)fathers.get(dest.getID());
//		if(trace == null)
//			value = -1;
//		
//		return value;
//
//	}
	
	public int illegalPathTo(Position src, Position dest, Vector queue, Vector passed) {
		int qSize = queue.size();

		Position n;
		Position u;
		Vector neighbours;

		if(qSize==0)
			return 0;

		while(qSize>0) {
			// Grab from queue
			n = (Position)queue.firstElement();
		//	System.out.println("" +n.getID());

			if(n == dest)
				return 1;
			
			// find neighbours of item
			neighbours = n.getNeighbours();

			if(!passed.contains(n)) {
				// traverse all neighbours of queue
				for(int j=0;j<neighbours.size();j++) {
					u = (Position)neighbours.elementAt(j);
					// add all neighbours to queue
					if(passed.contains(u) == false && queue.contains(u) == false) {
						//System.out.println("+" +u.getID());
						queue.add(u);
						fathers.put(u.getID(), n);
					}
				}
			}

			// mark this as viewed
			passed.add(n);

			// take item out of queue
			queue.remove(queue.firstElement());
			qSize--;

		}
		return illegalPathTo(src, dest, queue, passed) + 1;
	}

	 
	public int validPathTo(Position src,Position dest,Vector queue,Vector passed) {
		int qSize = queue.size();

		Position n;
		Position u;
		Vector neighbours;

		if(qSize==0)
			return 0;

		while(qSize>0) {
			// Grab from queue
			n = (Position)queue.firstElement();

			if(n == dest)
				return 1;
	
			// find neighbours of item
			neighbours = n.getNeighbours();

			if (!passed.contains(n)) {
				// traverse all neighbours of queue
				for (int j = 0; j < neighbours.size(); j++) {
					u = (Position) neighbours.elementAt(j);
					
					// add all neighbours to queue
					if (passed.contains(u) == false && queue.contains(u) == false) {
						boolean badLink = false;

						
						/**
						 * Intermediate rooms MUST be ultimate node.
						 */
						if(src instanceof Room) {
							if(u instanceof Room && u != dest) {
								badLink = true;
							}
						}
						/**
						 * If next node is room and node isn't destination.
						 */
						if(u instanceof Room == true) {
							if(u != dest) {
								badLink=true;
							}
						}
						
						if(n instanceof Room && (n != src && n != dest)) {
							badLink=true;
					//		System.out.println("failed here, c=" +u.getID());
						}
						
						/**
						 * Any square occupied not allowed
						 */
						if (u instanceof Square == true || u instanceof StartingSquare == true) {
							if(u.isOccupied() == true) {
						//		System.out.println("u=" + u.getID() + ",occupied=" + u.isOccupied());
								badLink = true;
							}
						}
						
						if(u instanceof Room) {
							if(u != dest)
								badLink=true;
							if(n instanceof Room == true) {
								/*
								 * Room to room transition only allowed if N == SRC and
								 * U == DEST
								 */
								if (n != src && u != dest)
									badLink = true;								
								
							}
						}

						if ((u instanceof StartingSquare == true || u instanceof Square == true) && n instanceof Room == true) {
							if (src instanceof Room == true && n != src)
								badLink = true;
							
						}

							/*
							 * else if(u instanceof Room == true && ( n != src && u !=
							 * dest)) { System.out.println("room="
							 * +u.getID()+",last="+n.getID()); passed.add(u); }
							 */
						if (badLink == true) {
							passed.add(u);
						}
						else {
							queue.add(u);
							fathers.put(u.getID(), n);
						}
					}
				}
			}

			// mark this as viewed
			passed.add(n);

			// take item out of queue
			queue.remove(queue.firstElement());
			qSize--;

		}
		return validPathTo(src,dest,queue,passed)+1;
	}
}
